Michał Maternik 126417 Piotr Błonski 225959
Wybrane funkcje testowe:¶
- Ackley
- Rastrigin
Wizualizacja funkcji ackley¶
Funkcja Ackley jest niewypukłą funkcją gdzie globalne optimum znajduje sie w punkcie f(0,0)=0. Wzór: $f(x,y)=-20exp[-2.0 \sqrt{-0.5(x^2+y^2)}] - epx[0.5(cos2\pi x + cos 2\pi y)]+e + 20 $
Posiada wiele minimów lokalnych co widać na poniższej wizualizacji
Wizualizacja funkcji ackley¶
from TestFunctions import *
from Visualization import *
from GWO import GWO
max_verticles = 5000
Visualize_Test_function(ackley_function,lb=-10,ub=10,function_points=max_verticles)
Wizualizacja funkcji Rastrigin¶
$f(x) = An + \sum_{i=1}^{n} [x_i^2-A cos(2\pi x_i)] $
Posiada globalne minimum w punkcie (0,0) i minimum to wynosi 0. Jest problematyczna ze względu na dużą przestrzeń do przeszukania jak i dużą ilość minimum lokalnych
Visualize_Test_function(Rastrigin_2D,lb=-10,ub=10,function_points=max_verticles)
from Visualization import *
from GWO import GWO
from PSO import PSO
from TCO import TCO
GWO - opis intucji¶
Algorytm GWO (Grey wolf optymaliztion) biologicznie nawiązuje do polujących szarych wilków. W naturze wilki dzielą się na rangi jednakże w tym algorytmie dzielimy wilki tylko na :Alpha, Beta, Delta, omega. Gdzie pierwsze 3 są pokolei najlepszymi znalezionymi rozwiązaniami. Wilki omega to rozwiązania które nie są Alphą/Betą/Deltą.
Stado wilków podejmuje decyzje o przeszukaniu terenu na podstawie pozycji Alfy Bety i Delty. Wilki podczas polowania okrążają swoją ofiare co odwzorowuje sposób obliczania wektora ruchu złożonego z wektorów: A - wektor obliczany obliczany na podstawie malejącego atrybutu 'a' co iteracje i losowych wektorów $r_1$ i $r_2$ w [0,1]
$\vec{A} = 2\vec{a} * \vec{r_1} - \vec{a}$
Następnie obliczany jest wektor C:
$\vec{C} = 2*\vec{r_2} $
Kierunek ruchu wilka:
$\vec{D} = $Stara_pozycja_ofiary$ *\vec{C} - $pozycja wilka$
Te wektory składają się na modyfikacje wektora ruchu każdego z prowadzących wilków. Pozostałe wilki $\omega$ poruszają się o średnią artmetyczną sumy wektorów ruchu wilków prowadzących.
Jako jedyny hiperparametr używamy granicy na której wilki polują. czyli 4 współrzędnych x1 x2 y1 y2 w naszym wypadku.
animate_paths(ackley_function,GWO,function_points = max_verticles,epoch=30,agents_size=100)
animate_paths(Rastrigin_2D,GWO,lb=-10, ub=10,function_points=max_verticles,epoch=30,agents_size=100)
PSO - opis intucji¶
PSO czyli Particle swarm optimalization działa na następującej zasadzie. Poczatkowo cząsteczki są losowo rozrzucone i mają losowy kierunek eksploracji. Typowana jest najlepsza cząsteczka, a każda cząsteczka pamięta swoją najlepszą pozycje.
Co iteracje ruch cząsteczek odbywa się na zasadzie złożenia wektorów: kierunek poprzedniego ruchu, osobista najlepsza pozycja, najlepsza pozycja w całym roju. Współczynniki C1 i C2 powinny maleć co iteracja a mają wpływ na to jak bardzo cząsteczka bierze pod uwagę swoją najlepszą pozycje a najlepszą pozycje roju. U nas C1 i C2 są zawsze na poziomie C1=1 i C2=2 Aby pozycja najlepsza z roju miała najwięcej wpływu. Dodatkowo c1 obniża się o 1/liczba epok co iteracje.
animate_paths(ackley_function,PSO,function_points = max_verticles,epoch=30,agents_size=100)
animate_paths(Rastrigin_2D,PSO,lb=-10, ub=10,function_points=max_verticles,epoch=30,agents_size=100)
TCO - opis intucji¶
W algorytmie TCO (Termite Colony Optimization), populacja termitów startuje wybranych pozycji początkowych należących do przeszukiwanej domeny funkcji i pozostawia ilość feromonów proporcjonalną do wartości funkcji celu. W kolejnych krokach osobniki przemieszczają się stochastycznie w kierunku zależnym od pozycji najlepszego z obecnych w ich otoczeniu znalezionego punktu (najlepszy to taki, w którym znajduje się największa ilość pozostawionego feromonu).
Feromony wyparowują ze współczynnikiem $\rho$, a ilość pozostawiana w kolejnej iteracji dana jest wzorem:
$\tau_i(t)=(1-\rho) \tau_i (t - 1) + \frac{1}{fit(x_i)+1}$, gdzie $\tau_i(t)$ jest warością feromonu pozostawionego w momencie $t$ przez osobnika $i$
animate_paths(ackley_function,TCO,lb=-10, ub=10,function_points=max_verticles,epoch=30,agents_size=100)
animate_paths(Rastrigin_2D,TCO,lb=-10, ub=10,function_points=max_verticles,epoch=30,agents_size=100)
Porównanie wyników na funkcjach testowych¶
from comparasion import *
Rastrigin¶
research(Rastrigin_2D,epoch=50,particle_size=100)
Ackley¶
research(ackley_function,epoch=50,particle_size=100)
Wnioski¶
- Algorytmy rojowe są dość proste w implementacji, i skuteczne jeśli chodzi o optymalizowanie funkcji z dużą ilością minimów/maksimów lokalnych
- Algorytm Mrówkowy (ACO) jest oparty o szukanie ścieżek w grafach natomiast jego ciągła odmiana czyli algorytm Termitowy nadaje się do optymalizowanie funkcji.
- Niektóre artykuły naukowe mówiące o tych algorytmach nie są dość zrozumiałe za pierwszym razem.
- Algorytm Termitowy wymaga więcej agentów niż algortym szarych wilkow czy cząsteczek
- Wbrew pozorom algorytm szarych wilków okazał się być lepszy niż algorytm cząsteczek, pomimo że jego implementacja jest prostrza w zrozumieniu i do napisania.
- Podczas algorytmów optymalizacyjnych określamy granice w których algorytmy te szukają optimów.
- Po kilku próbach zauważyliśmy ze algorytm termitowy ma tendencje do pozostawaniu w minimum lokalnym, algorytmowi cząsteczkowemu też czasem się to zdarzało. Algorytm szarych wilków wykazał największą odporność jeśli chodzi o ten problem.
- Algorytm cząsteczkowy posiada parametry które zmieniają podejmowanie decyzji przez cząsteczki. Podczas optymalizowania zmniejszanie parametru odpowiedzialnego za udział np najlepszego osobistego wyniku w czasie spowoduje że najlepszy wynik roju będzie miał większe znaczenie.
- Pomimo tego że obydwie funkcje testowe wykazują dużą ilość minimów lokalnych, ze względu na ich rozłożenie w funkcji Rastrigin, algorytmy TSO i PSO gorzej sobie radzą.
- Nawet jeśli wilki (agenci) w algorytmie szarych wilków mają początkowe pozycje dalekie od globalnego minimum to świetnie sobie radzą ze swoją taktyką obkrązania minimów lokalnych.
Źródła:¶
PSO¶
WZSI - Wykłady 2020 - Politechnika wrocławska